﻿//Write a program that reads three integer numbers N, K and S and an array of N elements from the console.
//Find in the array a subset of K elements that have sum S or indicate about its absence.


using System;
using System.Collections.Generic;

public class SubsetOfElementsEqualToGivenSum
{
    public static void Main()
    {
        Console.Write("Enter sum S = ");
        int sum = int.Parse(Console.ReadLine());
        Console.Write("Enter subset length K = ");
        int subsetCount = int.Parse(Console.ReadLine());
        Console.Write("Enter element number N = ");
        int elementCount = int.Parse(Console.ReadLine());
        Console.WriteLine("Enter {0} numbers", elementCount);
        int[] numbers = new int[elementCount];
        for (int i = 0; i < elementCount; i++)
        {
            numbers[i] = int.Parse(Console.ReadLine());
        }
        Console.WriteLine();

        int zeroSumCount = 0;
        for (int combinationCount = 1; combinationCount < Math.Pow(2, elementCount); combinationCount++)
        {
            int tempSum = 0;
            List<int> combination = new List<int>();
            combination = GetCombination(combinationCount);

            for (int j = 0; j < combination.Count; j++)
            {
                tempSum += numbers[combination[j]];
            }
            if (sum == tempSum)
            {
                if (combination.Count == subsetCount)
                {
                    zeroSumCount++;
                    Console.Write('{');
                    for (int k = 0; k < combination.Count; k++)
                    {
                        if (k < combination.Count - 1)
                        {
                            Console.Write("{0}, ", numbers[combination[k]]);
                        }
                        else
                        {
                            Console.Write("{0}", numbers[combination[k]]);
                        }

                    }
                    Console.Write("}\n");
                }
            }
        }
        if (zeroSumCount == 0)
        {
            Console.WriteLine("Subset of {0} elements that have sum {1} is absent.", subsetCount, sum);
        }
        else
        {
            Console.WriteLine("The number of combinations are {0}", zeroSumCount);
        }
    }

    private static List<int> GetCombination(int count)
    {
        string binaryLength = Convert.ToString(count, 2);
        List<int> combination = new List<int>();
        for (int i = 0; i < binaryLength.Length; i++)
        {
            int mask = 1;
            if ((count & mask) == 1)
            {
                combination.Add(i);
            }
            count >>= 1;
        }

        return combination;
    }
}